# 路径总和： https://leetcode-cn.com/problems/path-sum/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 这道题颇具研究价值 和 回溯启蒙学习，视频讲解也很详细，一步步来
# 自己的写法，能运行，但是感觉写的很怪，没啥条理，很乱~
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """
            抓住题目的一句话，是否存在 根节点到叶子节点 的路径！ 那么问题就锁定为了：
            前序遍历，求路径节点值相加是否等于 目标值
        """
        def dfs(node, targetSum):
            if not node: return False
            total = targetSum - node.val
            # 如果是叶子结点，进行判断是否 和为 targetSum
            if not node.left and not node.right: 
                if total == 0:
                    return True 
                # 这里else去掉也行，因为叶子结点不符合， 下一节点为 None， 照样返回False
                else:
                    return False  

            return dfs(node.left, total) or dfs(node.right, total) 

        return dfs(root, targetSum)

# 我的思路看下老师的代码竟然一样哈哈， 突然觉得不怪了


# 优化一下上面的if else写法 
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """
            抓住题目的一句话，是否存在 根节点到叶子节点 的路径！ 那么问题就锁定为了：
            前序遍历，求路径节点值相加是否等于 目标值
        """
        def dfs(node, targetSum):
            if not node: return False
            total = targetSum - node.val
            # 如果是叶子结点，进行判断是否 和为 targetSum
            if not node.left and not node.right and total == 0: 
                    return True  

            return dfs(node.left, total) or dfs(node.right, total) 

        return dfs(root, targetSum)